from sortedcontainers import SortedList

# 写一下这种解题方法的思路：
# 首先，本题所谓的“离最近的人最远”，其实指的是：当坐在某个间隔[a, b]内，a和b是离得最近的人，最远的座位就是(a+b)//2
# 因此，为了使之能够“最远”，就要选择在最大间隔的中间，那么其对应的特例是正好在最左或者最右
# 
class ExamRoom:
    def __init__(self, n: int):
        # 计算座位
        def dist(x: tuple) -> int:
            l, r = x
            if l == -1 or r == n:
                return r - l - 1
            else:
                return (r - l) // 2
        
        self.n = n
        # 间隔
        self.ts = SortedList(key=lambda x:(-dist(x), x[0]))
        self.left ={}
        self.right = {}
        self.add((-1, n))


    def seat(self) -> int:
        s = self.ts[0]
        
        if s[0] == -1:
            p = 0
        elif s[1] == self.n:
            p = self.n - 1
        else:
            p = (s[0] + s[1]) // 2
        
        self.delete(s)
        self.add((s[0], p))
        self.add((p, s[1]))
        return p


    def leave(self, p: int) -> None:
        l, r = self.left[p], self.right[p]
        self.delete((l, p))
        self.delete((p, r))
        self.add((l, r))
    

    def add(self, s:tuple):
        self.left[s[1]] = s[0]
        self.right[s[0]] = s[1]
        self.ts.add(s)
    
    
    def delete(self, s:tuple):
        self.ts.remove(s)
        self.left.pop(s[1])
        self.right.pop(s[0])


# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(n)
# param_1 = obj.seat()
# obj.leave(p)

if __name__ == "__main__":
    input_a = ["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
    input_b = [[10], [], [], [], [], [4], []]
    for i in range(len(input_a)):
        a = input_a[i]
        b = input_b[i]
        if a == "ExamRoom":
            obj = ExamRoom([b])
        elif a == "seat":
            print(obj.seat())
        elif a == "leave":
            obj.leave(b)